
public class Leetcode2044 {
    public static void main(String[] args) {
        System.out.println(countMaxOrSubsets(new int[]{3, 1}));
    }

//    public static int countMaxOrSubsets(int[] nums) {
//        int n = nums.length;
//        int max = Integer.MIN_VALUE;
//        int maxNumber = 0;
//
//        int count = 1 << n;
//        for (int i = 1; i < count; i++) {
//            int current = 0;
//            for (int j = 0; j < n; j++) {
//                if ((i & (1 << j)) != 0) {
//                    current |= nums[j];
//                }
//            }
//
//            if (current > max) {
//                max = current;
//                maxNumber = 1;
//            } else if (max == current) {
//                ++maxNumber;
//            }
//        }
//
//        return maxNumber;
//    }

    private static int max = 0;
    private static int res = 0;

    public static int countMaxOrSubsets(int[] nums) {
        for (int num : nums) {
            max |= num;
        }

        dfs(nums, 0, 0);

        return res;
    }

    private static void dfs(int[] nums, int index, int value) {
        if (value == max) {
            res += 1 << (nums.length - index);
            return;
        }

        if (index == nums.length) {
            return;
        }


        dfs(nums, index + 1, value);
        dfs(nums, index + 1, value | nums[index]);
    }
}

